package com.markus.code.动态规划;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/17 17:13
 * todo: 最长公共子序列的长度
 */
public class LeetCode_516 {
    /**
     * 之前讨论了用这个字符串的倒置串，两个组成行列模型来做这道题
     * 这次讨论如何用范围尝试的模型来把它做出来
     * 先来说下什么是范围尝试：
     *      我们尝试在[L...R]范围内解决这个问题，最终回归到[0,len-1]整体的问题
     * 这道题我们分为四种可能性：
     *      1、既不以L开头，也不以R结尾，所以只需要解决[L+1...R-1]即可
     *          dp[L][R] = dp[L+1][R-1]
     *      2、以L开头，不以R结尾
     *          dp[L][R] = dp[L][R-1]
     *      3、不以L开头，以R结尾
     *          dp[L][R] = dp[L+1][R]
     *      4、以L开头，以R结尾  !!! 前提【L】==【R】
     *          dp[L][R] = dp[L+1][R-1]+2
     */
    public int longestPalindromeSubseq(String s) {
        if (s == null || s.length() == 0){
            return 0;
        }
        if (s.length() == 1){
            return 1;
        }
        if (s.length() == 2){
            return s.charAt(0)==s.charAt(1)?2:1;
        }
        char[] str = s.toCharArray();
        //声明dp表
        int[][] dp = new int[str.length][str.length];
        //先填基本数据
        for (int i=0;i<dp.length;i++){
            dp[i][i] = 1;
            if (i!=dp.length-1){
                dp[i][i+1] = str[i]==str[i+1]?2:1;
            }
        }
        //普遍数据  从左往右、从上到下填
        for (int i=dp.length-3;i>=0;i--){
            for (int j=i+2;j<dp[i].length;j++){
                dp[i][j] = Math.max(Math.max(dp[i+1][j-1],dp[i+1][j]),dp[i][j-1]);
                if (str[i] == str[j]){
                    dp[i][j] = Math.max(dp[i][j],dp[i+1][j-1]+2);
                }
            }
        }
        return dp[0][str.length-1];
    }

    public static void main(String[] args) {
        String s = "bbbab";
        LeetCode_516 demo = new LeetCode_516();
        System.out.println(demo.longestPalindromeSubseq(s));
    }
}
